/**
  题目:
		
	还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

	输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
	
	示例 1:
	
	输入: [1,1,2,2,2]
	输出: true
	
	解释: 能拼成一个边长为2的正方形，每边两根火柴。
	示例 2:
	
	输入: [3,3,3,3,4]
	输出: false
	
	解释: 不能用所有火柴拼成一个正方形。
	注意:
	
	给定的火柴长度和在 0 到 10^9之间。
	火柴数组的长度不超过15。
 

 
 
   思路:
      1. 递归加会说 
	  
       
    
*/








class Solution {
public:
    bool makesquare(vector<int>& nums) {
        int size=nums.size();
        if(size<4){
            return false;
        }
        int sum=0;
        for(const auto&it:nums){
            sum+=it;
        }
        if(sum%4!=0){
            return false;
        }
        return dfs(nums,0,0,0,0,  0,sum/4);
    }
    bool dfs(vector<int>& nums,int index,int a,int b,int c,int d,int goal){
        if(index==nums.size()){
            //看看是否能满足
            if(a==goal&&b==a&&c==b&&d==a){
                return true;
            }
            return false;
        }
         if (a > goal || b > goal || c > goal || d > goal) {
            // 只要有一个边大于边长，则不用进行下一步放置了
            return false;
        }
 
        return dfs( nums,  index+1,  a+nums[index],  b,  c,  d,  goal)
        ||dfs( nums,  index+1,  a,  b+nums[index],  c,  d,  goal)
        ||dfs( nums,  index+1,  a,  b,  c+nums[index],  d,  goal)
        ||dfs( nums,  index+1,  a,  b,  c,  d+nums[index],  goal);
    }
};